package main.leetcode.offer.firstround.from51to68;

import main.datastruc.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 54.二叉搜索树的第k大节点
 *
 * <p>给定一棵二叉搜索树，请找出其中第k大的节点。
 *
 * <p>
 *
 * <p>示例 1:输入: root = [3,1,4,null,2], k = 1 输出: 4
 *
 * <p>示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3 输出: 4
 *
 * <p>限制：1 ≤ k ≤ 二叉搜索树元素个数
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex54 {
    private int res = 0;
    private int count = 0;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.right = new TreeNode(4);
        System.out.println(new ex54().kthLargest(root, 1));
    }

    /** 递归 */
    public int kthLargest1(TreeNode root, int k) {
        if (root != null) {
            kthLargest(root.right, k);
            if (++count == k) {
                return (res = root.val);
            }
            kthLargest(root.left, k);
        }
        return res;
    }

    /** 迭代 */
    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        int count = 0;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.addLast(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pollLast();
                if (++count == k) {
                    return node.val;
                }
                node = node.right;
            }
        }
        return 0;
    }
}
